package com.sheng.leetcode.year2023.month06.day21;

import lombok.var;
import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author liusheng
 * @date 2023/06/21
 * <p>
 * LCP 41. 黑白翻转棋<p>
 * <p>
 * 在 n*m 大小的棋盘中，有黑白两种棋子，黑棋记作字母 "X", 白棋记作字母 "O"，<p>
 * 空余位置记作 "."。当落下的棋子与其他相同颜色的棋子在行、<p>
 * 列或对角线完全包围（中间不存在空白位置）另一种颜色的棋子，则可以翻转这些棋子的颜色。<p>
 * 「力扣挑战赛」黑白翻转棋项目中，将提供给选手一个未形成可翻转棋子的棋盘残局，<p>
 * 其状态记作 chessboard。若下一步可放置一枚黑棋，请问选手最多能翻转多少枚白棋。<p>
 * 注意：<p>
 * 若翻转白棋成黑棋后，棋盘上仍存在可以翻转的白棋，将可以 继续 翻转白棋<p>
 * 输入数据保证初始棋盘状态无可以翻转的棋子且存在空余位置<p>
 * <p>
 * 示例 1：<p>
 * 输入：chessboard = ["....X.","....X.","XOOO..","......","......"]<p>
 * 输出：3<p>
 * 解释：<p>
 * 可以选择下在 [2,4] 处，能够翻转白方三枚棋子。<p>
 * <p>
 * 示例 2：<p>
 * 输入：chessboard = [".X.",".O.","XO."]<p>
 * 输出：2<p>
 * 解释：<p>
 * 可以选择下在 [2,2] 处，能够翻转白方两枚棋子。<p>
 * <p>
 * 示例 3：<p>
 * 输入：chessboard = [".......",".......",".......","X......",".O.....","..O....","....OOX"]<p>
 * 输出：4<p>
 * 解释：<p>
 * 可以选择下在 [6,3] 处，能够翻转白方四枚棋子。<p>
 * <p>
 * 提示：<p>
 * 1 <= chessboard.length, chessboard[i].length <= 8<p>
 * chessboard[i] 仅包含 "."、"O" 和 "X"<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/fHi6rV">LCP 41. 黑白翻转棋</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCodeLCP41 {

    @Test
    public void test01() {
//        String[] chessboard = {"....X.", "....X.", "XOOO..", "......", "......"};
//        String[] chessboard = {".X.", ".O.", "XO."};
        String[] chessboard = {".......", ".......", ".......", "X......", ".O.....", "..O....", "....OOX"};
        System.out.println(new Solution().flipChess(chessboard));
    }
}

class Solution {
    private int m;
    private int n;
    private String[] chessboard;

    public int flipChess(String[] chessboard) {
        m = chessboard.length;
        n = chessboard[0].length();
        this.chessboard = chessboard;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (chessboard[i].charAt(j) == '.') {
                    ans = Math.max(ans, bfs(i, j));
                }
            }
        }
        return ans;
    }

    private int bfs(int i, int j) {
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{i, j});
        char[][] g = new char[m][0];
        for (int k = 0; k < m; ++k) {
            g[k] = chessboard[k].toCharArray();
        }
        int cnt = 0;
        while (!q.isEmpty()) {
            var p = q.poll();
            i = p[0];
            j = p[1];
            for (int a = -1; a <= 1; ++a) {
                for (int b = -1; b <= 1; ++b) {
                    if (a == 0 && b == 0) {
                        continue;
                    }
                    int x = i + a, y = j + b;
                    while (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'O') {
                        x += a;
                        y += b;
                    }
                    if (x >= 0 && x < m && y >= 0 && y < n && g[x][y] == 'X') {
                        x -= a;
                        y -= b;
                        cnt += Math.max(Math.abs(x - i), Math.abs(y - j));
                        while (x != i || y != j) {
                            g[x][y] = 'X';
                            q.offer(new int[]{x, y});
                            x -= a;
                            y -= b;
                        }
                    }
                }
            }
        }
        return cnt;
    }
}
